from typing import *
from cmath import inf


class Solution:
    def sumOfPowers(self, nums: List[int], k: int) -> int:
        """
        dp[i][k][v] 以i位置作为子序列最后一个数值
                    长度k
                    能量v的子序列数量
        """
        """
        枚举倒数第二个数值，于i位置枚举j∈[0,i-1]，
        此时，这个序列的能量v，
        v是不可能大于 nums[i] - nums[j]
        如果以j结尾长度k-1的子序列能量vv>=v ,这个序列在增加i位置时
        产生一个长度k能量为v的子序列，即dp[i][k][v] += dp[j][k-1][vv] vv>=v
        """
        #  在选定i，枚举j时，j之前再选择的数值，如果产生了一个小于v的能vv量且长度为x，那么dp[i][x+1][vv] += dp[j][x][vv]
        n = len(nums)
        d = [[DefaultDict(int) for _ in range(k + 1)] for _ in range(n)]
        nums.sort()
        for i in range(n):
            d[i][1][inf] = 1
            for j in range(i):
                dis = nums[i] - nums[j]
                for p in range(2, k + 1):
                    for v, val in d[j][p - 1].items():  # 前一个位置 p - 1
                        if v >= dis:
                            d[i][p][dis] += val
                        else:
                            d[i][p][v] += val
        ans = 0
        for i in range(n):
            for v, cnt in d[i][k].items():
                ans += v * cnt
                ans %= 1000000007
        return ans


class Solution:
    def sumOfPowers(self, nums: List[int], k: int) -> int:
        n = len(nums)
        d = [[DefaultDict(int) for _ in range(k + 1)] for _ in range(n)]
        nums.sort()
        for i in range(n):
            d[i][1][inf] = 1
            for j in range(i):
                dis = nums[i] - nums[j]
                for p in range(2, k + 1):
                    for v, val in d[j][p - 1].items():  # 前一个位置 p - 1
                        if v >= dis:
                            d[i][p][dis] += val
                        else:
                            d[i][p][v] += val
        ans = 0
        for i in range(n):
            for v, cnt in d[i][k].items():
                ans += v * cnt
                ans %= 1000000007
        return ans
